#include <stdio.h>
#include <stdlib.h>

//顶点的最大个数
#define MAX_VERtEX_NUM 20
//表示顶点之间的关系的变量类型
#define VRType int
//存储弧或者边额外信息的指针变量类型
#define InfoType char
//图中顶点的数据类型
#define VertexType int
//定义bool型常量
typedef enum {false,true} bool;
//设置全局数组，记录标记顶点是否被访问过
bool visted[MAX_VERtEX_NUM];

typedef struct {
    //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值
    VRType adj;
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    //存储图中顶点数据
    VertexType vexs[MAX_VERtEX_NUM];
    //二维数组，记录顶点之间的关系
    AdjMatrix arcs;
    //记录图的顶点数和弧（边）数
    int vexnum, arcnum;
}MGraph;
//孩子兄弟表示法的链表结点结构
typedef struct CSNode {
    VertexType data;
    //孩子结点,兄弟结点
    struct CSNode * firstChild, * nextsibling;
}CSNode, * CSTree;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G, VertexType v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for(; i < G->vexnum; i++) {
        if(G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if(i > G->vexnum) {
        printf("not found\n");
        return -1;
    }
    return i;
}
//构造无向图
void CreateDN1(MGraph * G) {
    //输入图含有的顶点数和弧的个数
    G->vexnum = 13;
    G->arcnum = 13;
    //初始化图含有的顶点数据
    for(int i = 0; i < G->vexnum; i++) {
        G->vexs[i] = i+1;
    }
    //在二维数组中添加弧的数据
    /*
    {
          1  2  3  4  5  6  7  8  9  10  11  12  13
     1    0  1  1  0  0  1  0  0  0  0   0   0   0
     2    1  0  0  0  0  0  0  0  0  0   0   0   1
     3    1  0  0  0  0  0  0  0  0  0   0   0   0
     4    0  0  0  0  1  0  0  0  0  0   0   0   0
     5    0  0  0  1  0  0  0  0  0  0   0   0   0
     6    1  0  0  0  0  0  0  0  0  0   0   0   0
     7    0  0  0  0  0  0  0  1  1  1   0   0   0
     8    0  0  0  0  0  0  1  0  0  1   0   0   0
     9    0  0  0  0  0  0  1  0  0  0   0   0   0
    10    0  0  0  0  0  0  1  1  0  0   0   0   0
    11    0  0  0  0  0  0  0  0  0  0   0   1   1
    12    1  0  0  0  0  0  0  0  0  0   1   0   1
    13    0  1  0  0  0  0  0  0  0  0   1   1   0
    }
    */
   for(int i = 0; i < G->vexnum; i++) {
        for(int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
        }
   }
   //无向图的二阶矩阵沿主对角线对称
   //V1-V2
   G->arcs[0][1].adj = 1;
   G->arcs[1][0].adj = 1;
   //V1-V3
   G->arcs[0][2].adj = 1;
   G->arcs[2][0].adj = 1;
   //V1-V6
   G->arcs[0][5].adj = 1;
   G->arcs[5][0].adj = 1;
   //V1-V12
   G->arcs[0][11].adj = 1;
   G->arcs[11][0].adj = 1;
   //V2-V13
   G->arcs[1][12].adj = 1;
   G->arcs[12][1].adj = 1;
   //V4-V5
   G->arcs[3][4].adj = 1;
   G->arcs[4][3].adj = 1;
   //V7-V8
   G->arcs[6][7].adj = 1;
   G->arcs[7][6].adj = 1;
   //V7-V9
   G->arcs[6][8].adj = 1;
   G->arcs[8][6].adj = 1;
   //V7-V10
   G->arcs[6][9].adj = 1;
   G->arcs[9][6].adj = 1;
   //V8-V10
   G->arcs[7][9].adj = 1;
   G->arcs[9][7].adj = 1;
   //V11-V12
   G->arcs[10][11].adj = 1;
   G->arcs[11][10].adj = 1;
   //V11-V13
   G->arcs[10][12].adj = 1;
   G->arcs[12][10].adj = 1;
   //V12-V13
   G->arcs[11][12].adj = 1;
   G->arcs[12][11].adj = 1;
}

void CreateDN(MGraph * G) {
    //输入图含有的顶点数和弧的个数
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    //输入图含有的顶点数据
    for(int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    //初始化图
    for(int i = 0; i < G->vexnum; i++) {
        for(int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
        }
    }
    //查找元素位置，记录弧
    for(int i = 0 ; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d,%d",&v1,&v2);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if(m == -1 || n == -1) {
            printf("not found\n");
            return;
        }
        //无向图的二阶矩阵沿主对角线对称
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;
    }
}
//第一个相邻顶点
int FirstAdjVex(MGraph G, int v) {
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; i < G.vexnum; i++) {
        if(G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}
//下一个相邻顶点
int NextAdjVex(MGraph G, int v, int w) {
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for(int i = w+1; i < G.vexnum; i++) {
        if(G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

void DFSTree(MGraph G, int v, CSTree * T) {
    //将正在访问的该顶点的标志位设为true
    visted[v] = true;
    bool first = true;
    CSTree q = NULL;
    //依次遍历该顶点的所有邻接点
    for(int w = FirstAdjVex(G, v); w >=0; w = NextAdjVex(G, v, w)) {
        //如果该邻接点标志位为false，说明还未访问
        if(!visted[w]) {
            //为该邻接点初始化为结点
            CSTree p = (CSTree)malloc(sizeof(CSNode));
            p->data = G.vexs[w];
            p->firstChild = NULL;
            p->nextsibling = NULL;
            //该结点的第一个邻接点作为孩子结点，其它邻接点作为孩子结点的兄弟结点
            if(first) {
                (*T)->firstChild = p;
                first = false;
            } else {
                //否则，为兄弟结点
                q->nextsibling = p;
            }
            q = p;
            //以当前访问的顶点为树根，继续访问其邻接点
            DFSTree(G, w, &q);
        }
    }
}
//深度优先搜索生成森林并转化为二叉树
void DFSForest(MGraph G, CSTree * T) {
    (*T) = NULL;
    //每个顶点的标记为初始化为false
    for(int v = 0; v < G.vexnum; v++) {
        visted[v] = false;
    }
    CSTree q = NULL;
    //遍历每个顶点作为初始点，建立深度优先生成树
    for(int v = 0; v < G.vexnum; v++) {
        if(!visted[v]) {
            //新建一个结点，表示该顶点
            CSTree p = (CSTree)malloc(sizeof(CSNode));
            p->data = G.vexs[v];
            p->firstChild = NULL;
            p->nextsibling = NULL;
            //如果树为空，则该顶点作为树的树根
            if(!(*T)) {
                (*T) = p;
            } else {
                //该顶点作为树根的兄弟结点
                q->nextsibling = p;
            }
            //每次都要把q指针指向新的结点，为下次添加结点做铺垫
            q = p;
            //以该结点为起始点，构建深度优先生成树
            DFSTree(G, v, &p);
        }
    }
}

void PrintGraph(MGraph G) {
    for(int i = 0 ; i < G.vexnum; i++) {
        for(int j = 0; j < G.vexnum; j++) {
            printf("%d ", G.arcs[i][j].adj);
        }
        printf("\n");
    }
}

//前序遍历二叉树
void PreOrderTraverse(CSTree T) {
    if(T) {
        printf("%d ", T->data);
        PreOrderTraverse(T->firstChild);
        PreOrderTraverse(T->nextsibling);
    }
    return;
}

int main(int argc, char * argv[]) {
    //建立一个图的变量
    MGraph G;
    //调用创建函数，传入地址参数
    CreateDN1(&G);
    //调用创建函数，传入地址参数
    //CreateGraph(&G);
    //输出图的二阶矩阵
    PrintGraph(G);
    printf("\n");
    CSTree T;
    //深度优先搜索森林
    DFSForest(G, &T);
    PreOrderTraverse(T);
    return 0;
}